package com.cuz.daileetcode;

import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;

/***
 * 第350题：两个数组的交集
 * 给定两个数组，编写一个函数来计算它们的交集。
 * 示例 1:
 *
 * 输入: nums1 = [1,2,2,1], nums2 = [2,2]
 *
 * 输出: [2,2]
 * 示例 2:
 *
 * 输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
 *
 * 输出: [4,9]
 * 说明：
 *
 * 输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
 * 我们可以不考虑输出结果的顺序。
 * 进阶:
 *
 * 如果给定的数组已经排好序呢？将如何优化你的算法呢？
 */
public class Day21 {

    public int[] intersect(int[] nums1, int[] nums2) {
        int index1 = 0;
        int index2 = 0;
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        LinkedList<Integer> listRes = new LinkedList<>();
        while (index1 < nums1.length && index2 < nums2.length) {
            if (nums1[index1] == nums2[index2]) {
                listRes.add(nums1[index1]);
                index1++;
                index2++;
            } else if (nums1[index1] > nums2[index2]) {
                index2++;
            } else {
                index1++;
            }
        }
        return listRes.stream().mapToInt(Integer::intValue).toArray();
    }
}
